package org.basic.algorithm.others;

/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
 *
 * @author 李坤
 * @date 2022/9/5 15:47
 */
public class Steps {

    public static void main(String[] args) {
        System.out.println(calculate(4));
    }

    private static int calculate(int level) {
        final int[] cache = new int[level];
        cache[0] = 1;
        cache[1] = 2;

        return recursionCalculate(level - 1, cache);
    }

    private static int recursionCalculate(int level, int[] cache) {
        int value = cache[level];
        // 为什么 cache[n] = cache[n-1] + cache[n-2] ？
        return value == 0 ? recursionCalculate(level - 1, cache) + recursionCalculate(level - 2, cache) : value;
    }

}
